package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 08 - 06
 * Time:10:57
 */

/**
 * 重排链表
 * 如     1 ——>2 ——> 3 ——> 4
 * 变成 ： 1 ——> 4 ——? 2 ——> 3
 */
public class Test5 {
    public void recorderList(ListNode head){
        if(head == null){
            return;
        }
        //(1)找到链表的中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow;
        ListNode start = head;
        ListNode end = mid.next;
        mid.next = null;//将两个链表从中间节点进行断开，并i企鹅将第一部=部分的链表的next设置为null
        //(2)将链表的后半部分进行反转
        ListNode cur = end;
        ListNode newHead = null;
        ListNode prev = null;
        while(cur != null){
            ListNode curNext = cur.next;
            if(curNext == null){
                newHead = cur;
            }
            cur.next = curNext;
            prev = cur;
            cur = curNext;
        }

        //(3)合并两个链表
        while(start != null && end != null){
            ListNode next1 = start.next;
            ListNode next2 = end.next;
            start.next = end;
            end.next = next1;
            start = next1;
            end = next2;
        }
        return;
    }
}
